package com.zp.self.module.level_4_算法练习.数学.数学推理;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_728_自除数 {
   static  List<Integer> list = new ArrayList<>();

    @Test
    public void main() {

        System.out.println(selfDividingNumbers(44,85));
    }

    /**
    题目：自除数 是指可以被它包含的每一位数整除的数。
         例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
         自除数 不允许包含 0 。
         给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数 。

     示例 1：
     输入：left = 1, right = 22
     输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

     示例 2:
     输入：left = 47, right = 85
     输出：[48,55,66,77]

    分析：【P 💔💔】
       1.蛮力法：....
            --执行用时：2 ms, 在所有 Java 提交中击败了48.93%的用户
            --时长：14分钟
       大神：在static 代码块中先求出所有结果，在根据不同的测试参数 ，二分法找出结果即可

    边界值 & 注意点：
       1.
     **/
    public static List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> res = new ArrayList<>();
        while (left<=right){
            int numb=left;
            while (numb>0){
                int yu = numb % 10;
                if(yu==0 || left%yu!=0)
                    break;
                numb =numb / 10;
            }
            if(numb==0)
                res.add(left);
            left++;
        }
        return res;
    }

    static {
        list=selfDividingNumbers(1, 10000);
    }
    //大神：在static 代码块中先求出所有结果，在根据不同的测试参数 ，二分法找出结果即可
    public List<Integer> selfDividingNumbers2(int left, int right) {
        List<Integer> ans = new ArrayList<>();
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (list.get(mid) >= left) //找到左边第一个满足的数。
                r = mid;
            else
                l = mid + 1;
        }
        while (r < list.size() && list.get(r) <= right) //逐渐向右靠拢
            ans.add(list.get(r++));
        return ans;
    }

}
